LinHuijuan's Blog

动态规划（DP算法）

# 动态规划（DP算法）

[TOC]

# 一、动态规划

# 1.1 固定的流程

  • 以斐波那契数列为例。
    • 1、1、2、3、5、8、13、21、34、……

# 1.1.1 递归暴力解法

function fib(n) {
    if (n===0 || n===1) return n;
    return fib(n-1) + fib(n-2)
}
1
2
3
4

时间复杂度：O(2^n)，指数爆炸。

待解决：大量的重复计算。

# 1.1.2 带备忘录的递归解法

解决方法：

  1. 先将每一个计算的答案记在备忘录里。
  2. 计算前先去备忘录查查。
function fib(n) {
    if (n < 1) return 0;
    let memo = [];
    memo[1] = memo[2] = 1;
    return helper(memo, n);
}

function helper(memo, n) {
    if (n > 0 && !memo[n]) {
        memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
    }
    return memo[n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度O(n)

自顶向下，直到f(1)、f(2)触底才逐层返回答案。

# 1.1.3 非递归的动态规划解法

自底向上，从f(1)、f(2)开始往上推，知道推到想要的大难。

无需递归，由循环迭代完成计算。

function fib(n) {
    let dp = [];
    dp[0] = 0;
    dp[1] = 1;
    for(let i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}
1
2
3
4
5
6
7
8
9
# 1.1.3.1 状态转移方程（核心）

其实就是f(n) = f(n-1) + f(n-2)。

实际上，我们只需要保存之前的两个状态，即空间复杂度为O(1)即可。

function fib(n) {
    if(n<2) return n;
    let prev = 0, cur = 1;
    for(let i = 2; i <= n; i++) {
        let sum = prev + cur;
        prev = cur;
        cur = sum;
    }
    return cur;
}
1
2
3
4
5
6
7
8
9
10

# 二、从凑零钱看最优子结构

给你 k 种面值的硬币，面值分别为 c1, c2 ... ck，再给一个总金额 n，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，则回答 -1 。

比如说，k = 3，面值分别为 1，2，5，总金额 n = 11，那么最少需要 3 枚硬币，即 11 = 5 + 5 + 1 。

# 2.1 状态转移方程

f(n)表示至少需要的硬币数

那么，n=0时，f(n) = 0;

n ≠ 0时，f(n) = 1 + min{f(n-ci) | i∈[1, k]}

# 2.2 最优子结构

  • 原问题的解由子问题的最优解构成。
  • 要符合最优子结构，子问题必须相互独立，互不干扰。
function coinChange(coins, amount) {
    let k = coins.length;
    let max = amount+1;
    let dp = new Array(amount+1).fill(max);
    dp[0] = 0;
    for (let i = 1; i <= amount; i++) {
        for (let j = 0; j < k; j++) {
            if(coins[j] <= i) {
                dp[i] = Math.min(dp[i], 1+ dp[i - coins[j]]);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 三、正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符 '*' 匹配零个或多个前面的那一个元素 所谓匹配，是要涵盖整个字符串s的，而不是部分字符串。

说明:

s 可能为空，且只包含从 a-z 的小写字母。 p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

示例 1:

输入: s = "aa" p = "a" 输出: false

示例 2:

输入: s = "aa" p = "a*" 输出: true

示例 3:

输入: s = "ab" p = ".*" 输出: true

示例 4:

输入: s = "aab" p = "cab" 输出: true 解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5:

输入: s = "mississippi" p = "misisp*." 输出: false

# 3.1递归暴力解法

var isMatch = function (s, p) {
    if (s === p) return true;
    let isFirstMatch = false;
    if (s && p) {
        if (s[0] === p[0] || p[0] === '.') {
            isFirstMatch = true;
        }
    }
    if (p.length > 1 && p[1] === '*') {
        // s:aaa p:ab*a*a
        // 下面这一步应该优先考虑
        if (isMatch(s, p.substring(2))) {
            return true;
        } else if (isFirstMatch) {
            return isMatch(s.substring(1), p);
        }
    }
    return isFirstMatch && isMatch(s.substring(1), p.substring(1));
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 3.2 带备忘录的递归解法

并没有重复计算的过程，无需备忘录。

# 3.3 非递归的动态规划

// 自底向上
/**
 * @param {string} string
 * @param {string} pattern
 * @return {boolean}
 */
var isMatch = function (s, p) {
    // 特殊情况
    if (s === p) return true;
    
    // 非特殊情况
    let sLen = s.length,
        pLen = p.length;
    
    // 1. 初始化 dp[i][j]
    // dp[i][j]表示s中前i个字符与p中前j个字符的匹配结果
    // 要将空串的情况考虑进来
    // 注意：dp下标与s,p对应元素的下表相差1
    // 也就是说，dp[i][j]表示当前应该匹配s[i-1]与p[j-1]
    let dp = new Array(sLen + 1);
    for (let i = 0; i <= sLen; i++) {
        dp[i] = new Array(pLen + 1);
    }

    // 2. 考虑空串的情况
    // 2.1 s、p都为空串的情况
    dp[0][0] = true;
    // 2.2 s不空，p空都为false
    for (let i = 1; i <= sLen; i++) {
        dp[i][0] = false;
    }
    // 2.3 s空，但p为a*b*c*仍为true，否则为false
    dp[0][1] = false
    for (let j = 2; j <= pLen; j++) {
        dp[0][j] = p[j - 1] === '*' ? dp[0][j - 2] : false;
    }
    
    // 3. 非空串情况：从后往前考虑
    for (let i = 1; i <= sLen; i++) {
        for (let j = 1; j <= pLen; j++) {
            // 3.1 p的最后一位不为 *，但最后一位都相同，则都往前一位考虑
            if (s[i - 1] === p[j - 1] || p[j - 1] === '.') {
                dp[i][j] = dp[i - 1][j - 1];
            } 
            // 3.2 p的最后一位为 *
            else if (p[j - 1] === '*') {
                
                // s:aaa,p:ab*a*
                // 3.2.1 p往前两位仍为真，则往前两位考虑
                if (j-2>=0 && dp[i][j - 2]) {
                    dp[i][j] = dp[i][j - 2];
                } 
                // 3.2.2 否则如果当前s位同p的前一位匹配，则只将s往前移一位考虑
                else if (j-2>=0 && p[j - 2] === s[i - 1] || p[j - 2] === '.') {
                    dp[i][j] = dp[i - 1][j];
                } 
                // 3.2.3  都不符合，就为false
                else {
                    dp[i][j] = false;
                }
            } 
            // 3.3 // 都不符合，就为false
            else {
                dp[i][j] = false;
            }
        }
    }
    return dp[sLen][pLen];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

# 四、其他练习

# 4.1 leetcode-198-打家劫舍

* 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

* 给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

* 示例 1:

* 输入: [1,2,3,1]

* 输出: 4

* 解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。

* 偷窃到的最高金额 = 1 + 3 = 4 。

  • 官方题解

var rob = function(nums) {
    let prev = 0, cur = 0
    let len = nums.length
    for(let i = 0; i < len; i++) {
        let tmp = cur
        cur = Math.max(prev+nums[i], cur)
        prev = tmp
    }
    return cur
};
1
2
3
4
5
6
7
8
9
10

八皇后